import java.util.ArrayList;
import java.util.List;

/**
 * 633. 平方数之和
 * https://leetcode-cn.com/problems/sum-of-square-numbers/
 */
public class Solutions_633 {
    public static void main(String[] args) {
        int c1 = 5;  // output: true
        int c2 = 3;  // output: false
        int c3 = 4;  // output: true
        int c4 = 2;  // output: true
        int c5 = 1;  // output: true
        int c6 = 1000000;  // output: true

        List<Integer> inputs = new ArrayList<>();
        inputs.add(c1);
        inputs.add(c2);
        inputs.add(c3);
        inputs.add(c4);
        inputs.add(c5);
        inputs.add(c6);

        for (Integer input : inputs) {
            boolean result = judgeSquareSum(input);
            System.out.println(result);
        }
    }

    /**
     * 解题思路：双指针
     * 关键：4 = 0 * 0 + 2 * 2（数字 0 也是平方数）
     */
    public static boolean judgeSquareSum(int c) {
        int left = 1;
        int right = (int) Math.sqrt(c);
        if (right * right == c) {
            // 数字 c 本身就是一个平方数
            // 例如：4 = 0 * 0 + 2 * 2
            return true;
        }
        // 通过左右指针在 [left, right] 范围内，找到两个数，使其平方数之和等于 c
        while (left <= right) {
            int total = left * left + right * right;
            if (total == c) {
//                System.out.println(left + "---" + right);
                return true;
            } else if (total < c) {
                left ++;
            } else if (total > c) {
                right --;
            }
        }
        return false;
    }
}
